package com.linyaonan.leetcode.medium._2958;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * 一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。
 *
 * 如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。
 *
 * 请你返回 nums 中 最长好 子数组的长度。
 *
 * 子数组 指的是一个数组中一段连续非空的元素序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,1,2,3,1,2], k = 2
 * 输出：6
 * 解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。
 * 最长好子数组的长度为 6 。
 * 示例 2：
 *
 * 输入：nums = [1,2,1,2,1,2,1,2], k = 1
 * 输出：2
 * 解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
 * 最长好子数组的长度为 2 。
 * 示例 3：
 *
 * 输入：nums = [5,5,5,5,5,5,5], k = 4
 * 输出：4
 * 解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
 * 最长好子数组的长度为 4 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^9
 * 1 <= k <= nums.length
 *
 * @author: Lin
 * @date: 2024/10/29
 */
public class LengthOfLongestSubarrayWithAtMostKFrequency {

    /**
     * 仍然为不定长滑动窗口问题
     * @param nums
     * @param k
     * @return
     */
    public int maxSubarrayLength(int[] nums, int k) {
        int l = 0;
        int r = 0;

        Map<Integer, Integer> saved = new HashMap<>();
        int addLen = 0;
        int result = 0;
        while (l <= r && r < nums.length) {
            int current = nums[r];
            saved.merge(current, 1, Integer::sum);
            // 遍历到r位置的时候只需要考虑r这个数值对应的出现个数是否大于k，因为index=r之前的数值已经遍历过了是不会大于k个数的
            while (saved.getOrDefault(current, 0) > k) {
                int pre = nums[l];
                if (saved.merge(pre, -1, Integer::sum) == 0) {
                    saved.remove(pre);
                }
                l++;
                addLen--;
            }

            r++;
            addLen++;
            result = Math.max(result, addLen);
        }

        return result;
    }

    /**
     * 不能使用下面遍历的方式，会超市
     * @param saved
     * @param k
     * @return
     */
    private boolean hashOverK(Map<Integer, Integer> saved, int k) {
        for (Map.Entry<Integer, Integer> entry : saved.entrySet()) {
            if (entry.getValue() > k) {
                return true;
            }
        }

        return false;
    }

}
